package com.BinaryTree;

import com.SingleLinkedList.SingleLinkedList;
import com.SingleLinkedList.SingleLinkedListImplementation;

public class BinaryTreeImplementation<K extends Comparable<K>, V> implements
		BinaryTree<K, V> {

	private class Node {
		private K key;
		private V value;
		private Node leftChild;
		private Node rightChild;

		public Node() {
		}

		public Node(K key, V value) {
			this.key = key;
			this.value = value;
		}

		public String toString() {
			return String.format("[Key = %s; Value = %s]", key.toString(),
					value.toString());
		}
	}

	private Node root;
	private int size;

	@Override
	public void add(K key, V value) {
		
		if(key == null || value == null)
			throw new IllegalArgumentException("Null arguments are not allowed");

		Node newNode = new Node(key, value);
		if (root == null) {
			root = newNode;
			size++;
			return;
		}
		Node currentNode = root;
		while (true) {
			if (newNode.key.compareTo(currentNode.key) < 0)
				if (currentNode.leftChild != null) {
					currentNode = currentNode.leftChild;
					continue;
				} else {
					currentNode.leftChild = newNode;
					size++;
					return;
				}

			if (newNode.key.compareTo(currentNode.key) > 0)
				if (currentNode.rightChild != null) {
					currentNode = currentNode.rightChild;
					continue;
				} else {
					currentNode.rightChild = newNode;
					size++;
					return;
				}

			if (newNode.key.compareTo(currentNode.key) == 0) {
				currentNode.value = newNode.value;
				return;
			}
		}
	}

	@Override
	public boolean remove(K key) {
		if (key == null)
			return false;
		boolean isRemoved;
		if (root == null)
			return false;
		if (root.key.equals(key)) {
			Node temporaryRoot = new Node();
			temporaryRoot.leftChild = root;
			isRemoved = remove(key, root, temporaryRoot);
			root = temporaryRoot.leftChild;
			size--;
			return true;
		}

		isRemoved = remove(key, root, null);
		if (isRemoved) {
			System.out.println("Size decreased");
			size--;
		}
		return isRemoved;
	}

	private boolean remove(K key, Node current, Node parent) {
		if (key.compareTo(current.key) < 0) {
			if (current.leftChild != null)
				return remove(key, current.leftChild, current);
			else
				return false;
		} else if (key.compareTo(current.key) > 0) {
			if (current.rightChild != null)
				return remove(key, current.rightChild, current);
			else

				return false;
		} else {
			if (current.leftChild != null && current.rightChild != null) {
				Node minNodeInRightSubtree = getMinNode(current.rightChild);
				current.value = minNodeInRightSubtree.value;
				current.key = minNodeInRightSubtree.key;
				remove(current.key, current.rightChild, current);
			} else if (parent.leftChild == current) {
				parent.leftChild = (current.rightChild != null) ? current.rightChild
						: current.leftChild;
			} else if (parent.rightChild == current) {
				parent.rightChild = (current.rightChild != null) ? current.rightChild
						: current.leftChild;
			}
			return true;
		}
	}

	private Node getMinNode(Node root) {
		if (root == null)
			return null;
		while (root.leftChild != null)
			root = root.leftChild;
		return root;
	}

	private Node getNodeByKey(K key) {
		if (root == null)
			return null;
		Node currentNode = root;
		while (key.compareTo(currentNode.key) != 0) {
			if (key.compareTo(currentNode.key) < 0)
				currentNode = currentNode.leftChild;
			if (key.compareTo(currentNode.key) > 0)
				currentNode = currentNode.rightChild;
			if (currentNode == null)
				return null;
		}
		return currentNode;
	}

	private SingleLinkedList<Node> toListOfNodes() {
		SingleLinkedList<Node> result = new SingleLinkedListImplementation<Node>();
		if (root == null)
			return result;
		result.add(root);
		for (Node node : result) {
			if (node.leftChild != null)
				result.add(node.leftChild);
			if (node.rightChild != null)
				result.add(node.rightChild);
		}
		return result;
	}

	@Override
	public boolean containsValue(Object value) {
		if (value == null)
			return false;
		SingleLinkedList<Node> nodeList = toListOfNodes();
		for (Node node : nodeList) {
			if (node.value.equals(value))
				return true;
		}
		return false;
	}

	@Override
	public boolean containsKey(K key) {
		if (key == null)
			return false;
		return getNodeByKey(key) != null;
	}

	@Override
	public V get(K key) {
		if (key == null)
			return null;
		Node obtainedNode = getNodeByKey(key);
		return obtainedNode != null ? obtainedNode.value : null;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public void clear() {
		SingleLinkedList<Node> nodeList = toListOfNodes();
		for (Node node : nodeList) {
			remove(node.key);
		}
	}

	private void recursivePrintDepth(Node root) {
		if (root != null) {
			recursivePrintDepth(root.leftChild);
			System.out.println(root);
			recursivePrintDepth(root.rightChild);
		}
	}

	@Override
	public void printInWidth() {
		if (root == null) {
			System.out.println("[]");
			return;
		}
		SingleLinkedList<Node> nodeList = toListOfNodes();
		for (Node node : nodeList) {
			System.out.println(node);
		}
	}

	@Override
	public void printInDepth() {
		if (root == null) {
			System.out.println("[]");
			return;
		}
		recursivePrintDepth(root);
	}
}
